﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/sqrtx/
/*
题目描述：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：
输入：x = 4
输出：2

示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
*/

// 方法1——二分法
/*
思路：
由于平方根的整数部分ans满足，K^2 <= x，的最大解，因此我们可以对ans使用二分查找法。
当mid * mid <= x时，说明mid为可能的解，将mid赋值给ans，并扩大结果，执行left = mid + 1，
否则说明mid * mid的结果大于x，这就要缩小结果，执行right = mid - 1。
当left > right退出循环时，ans即为最终结果。
*/

// 有了以上思路，那我们写起代码来也就水到渠成了：
int mySqrt(int x) {
	int left = 0;
	int right = x;
	long long mid = 0;
	int ans = 0;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (mid * mid <= x) {
			ans = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return ans;
}
// 时间复杂度：O(log2N)，N即为x。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。